związek równoważności

Związek równoważności – w teorii mnogości oraz w logice pojęcie to określa szczególny rodzaj relacji binarnej, który spełnia trzy aksjomaty: zwrotność, symetrię i przechodniość. Dzięki tym własnościom każdy związek równoważności wyznacza podział zbioru na nieprzecinające się podzbiory zwane (klasami abstrakcji).

Definicja

Niech X będzie dowolnym zbiorem. Relacja R ⊆ X × X na X jest związkiem równoważności, jeżeli dla wszystkich elementów a, b, c ∈ X zachodzą następujące warunki:

Zwrotność: a R a (każdy element jest w relacji sam ze sobą).
Symetria: jeśli a R b, to b R a.
Przechodniość: jeśli a R b oraz b R c, to a R c.

Klasy abstrakcji i partycje

Dla dowolnego elementu x ∈ X definiujemy klasę abstrakcji (zwane też klasą równoważności) jako zbiór

[x] = { y ∈ X : x R y }.

Klasy abstrakcji mają następujące własności:

Każdy element zbioru X należy do dokładnie jednej klasy abstrakcji.
Dwie klasy są albo identyczne, albo rozłączne.
Zbiór klas abstrakcji tworzy partycję zbioru X.

Przykłady

Równość liczb: na zbiorze liczb całkowitych ℤ relacja „a = b” jest związkiem równoważności.
Równość modulo n: dla stałej naturalnej n > 0 relacja a ≡ b (mod n) dzieli ℤ na n klas abstrakcji, czyli na klasy reszt przy dzieleniu przez n.
Podobieństwo figur: dwie figury w płaszczyźnie są podobne, jeżeli istnieje przekształcenie afiniczne zachowujące proporcje boków. To jest związek równoważności w zbiorze wszystkich figur.
Izomorfizm grafów: dwa grafy są izomorficzne, jeżeli istnieje bijekcja między ich wierzchołkami zachowująca incydencję krawędzi. To także spełnia aksjomaty zwrotności, symetrii i przechodniości.

Zastosowania

Związki równoważności odgrywają kluczową rolę w wielu dziedzinach matematyki i informatyki:

W algebraicznej teorii grup klasy abstrakcji względem relacji koniugacji prowadzą do pojęcia klas koniugacji.
W topologii identyfikacja punktów według pewnych relacji prowadzi do konstrukcji przestrzeni ilorazowych.
W teorii automatów minimalizacja automatów wykorzystuje relację równoważności stanów.
W bazach danych pojęcie klucza naturalnego można traktować jako związek równoważności definiujący istnienie identycznych rekordów.

Formalne własności

Jeśli R jest związkiem równoważności na X, to możemy zdefiniować funkcję naturalną:

π : X → X/R, gdzie X/R oznacza zbiór klas abstrakcji, a π(x) = [x]. Funkcja π jest surjekcją i spełnia warunek:

dla a, b ∈ X zachodzi π(a) = π(b) wtedy i tylko wtedy, gdy a R b.

Powiązane pojęcia

Osoby zainteresowane tematem mogą również przeczytać o:

Literatura

J. Enderton, Elements of Set Theory, Academic Press, 1977.
K. Kuratowski, Set Theory and Logic, Państwowe Wydawnictwo Naukowe, 1994.
M. Sipser, Introduction to the Theory of Computation, Cengage Learning, 2012 – rozdział o minimalizacji automatów.